import java.util.Arrays;

public class UnionFindSet {
    public int[] elem;
    public int usedSize;

    public UnionFindSet(int n){
        this.elem = new int[n];
        Arrays.fill(this.elem, -1);
    }

    public int findRoot(int x) {
        if(x < 0){
            throw new PosOutOfBoundsException("输入的下标不合法，是负数！");
        }
        while(this.elem[x] >= 0){
            x = this.elem[x];
        }
        return x;
    }

    public boolean isSameUnionFindSet(int x1, int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);

        if(index1 == index2){
            return true;
        }else{
            return false;
        }
    }

    public void union(int x1, int x2){
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);

        if(index1 == index2){
            return;
        }

        this.elem[index1] = this.elem[index1] + this.elem[index2];
        this.elem[index2] = index1;
    }

    public int count(){
        int count = 0;
        for(int i = 0; i < this.elem.length; i++){
            if(this.elem[i] < 0) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(10);
        unionFindSet.union(0, 6);
        unionFindSet.union(0, 7);
        unionFindSet.union(0, 8);
        unionFindSet.union(1, 4);
        unionFindSet.union(1, 9);
        unionFindSet.union(2, 3);
        unionFindSet.union(2, 5);

        System.out.println(unionFindSet.isSameUnionFindSet(6, 9));

        unionFindSet.union(8, 1);

        System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
    }
}
